package GreedyAlgorithm;

/**
 * @author Liaorun
 */
public class ColorLeftRight {
    public static int minPaint(String s) {
        if (s == null || s.length() < 2) {
            return 0;
        }

        char[] chars = s.toCharArray();

        // 记录右边一共有多少个R的数组
        int[] right = new int[chars.length];

        right[chars.length - 1] = chars[chars.length - 1] == 'R' ? 1 : 0;

        for (int i = chars.length - 2; i >= 0; i--) {
            right[i] = right[i + 1] + (chars[i] == 'R' ? 1 : 0);
        }

        int res = right[0];
        int left = 0;

        for (int i = 0; i < chars.length - 1; i++) {
            left += chars[i] == 'G' ? 1 : 0;
            res = Math.min(res, left + right[i + 1]);
        }

        res = Math.min(res, left + (chars[chars.length - 1] == 'G' ? 1 : 0));
        return res;
    }

    public static void main(String[] args) {
        String test = "GGGGGR";
        System.out.println(minPaint(test));
    }
}
